class Solution {
    Node pre; // 记录当前节点的前一个结点
    Node head; // 指向头结点

    public Node treeToDoublyList(Node root) {
        if (root == null) return null; // 特殊情况
        dfs(root);
        // pre 指向最后一个节点  head指向第一个节点
        pre.right = head;
        head.left = pre;
        return head;
    }

    public void dfs(Node cur) {
        if (cur == null) return;
        dfs(cur.left);

        // 处理当前节点与他前一个节点的关系
        if (pre == null) head = cur;
        else pre.right = cur;
        cur.left = pre; // 将当前节点的left指针指向他的前一节点
        // 当前节点处理好了，这时候我们需要去处理下一个节点，所以当前节点就成为了下一个节点的前驱节点
        pre = cur; 
        
        dfs(cur.right);
    }
}
// 1 2 3 4 5
// pre <-> cur
// pre.right = cur  cur.left = pre